// 斐波拉契（黄金分割）查找算法
/**
 *
 * @param arr {Array} 数组 升序
 * @param findVal {number} 要查找的值
 */
function fibonacciSearch (arr, findVal) {
    let low = 0
    let high = arr.length - 1
    let k = 0 // 表示斐波那契分割下标
    let mid = 0
    let f = fibonacci(20)
    // 获取斐波那契分割下标
    while (high > f[k] - 1) {
        k++
    }
    let temp = [...arr]
    for (let i = high + 1; i < f[k]; i++) {
        temp[i] = arr[high]
    }
    while (low <= high) {
        mid = low + f[k - 1] - 1
        if (findVal < temp[mid]) { // 向左
            high = mid - 1
            // 全部元素 = 前面 + 后面 f[k]= f[k-1] + f[k-2]
            // 前面有 f[k-1] 继续拆分 f[k-1]= f[k-2] + f[k-3]
            // 即在f[k-1]的前面继续查找 k--
            k--
        } else if (findVal > temp[mid]) {  // 向右
            low = mid + 1
            // 全部元素 = 前面 + 后面 f[k]= f[k-1] + f[k-2]
            // 前面有 f[k-1] 继续拆分 f[k-2]= f[k-3] + f[k-4]
            // 即在f[k-2]的前面继续查找 k -= 2
            k -= 2
        } else {
            if (mid <= high) {
                return mid
            } else {
                return high
            }
        }
    }
    return -1
}

function fibonacci (maxSize) {
    let f = []
    f[0] = 1
    f[1] = 1
    for (let i = 2; i < maxSize; i++) {
        f[i] = f[i - 1] + f[i - 2]
    }
    return f
}

function main () {
    let arr = [1, 8, 10, 89, 1000, 1234]
    let index = fibonacciSearch(arr, 89)
    console.log(index)
}

main()
